package com.zy.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Created by zhaoyi on 2019/7/11
 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
 * https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/877/
 */
public class MinStack {

    //存放数据
    List<Integer> data = new ArrayList<Integer>();
    int index = 0;
    int minIndex = 0;

    public MinStack() {
    }

    public void push(int x) {
        if (index > 0 && x < data.get(minIndex)) {
            minIndex = index;
        }
        data.add(index, x);
        index++;
    }

    public void pop() {
        if (index > 0) {
            index--;
            if (index == minIndex && index > 0) {
                //找最小
                minIndex = index - 1;
                Integer tmpMin = data.get(index - 1);
                for (int i = 0; i < (index - 1); i++) {
                    if (data.get(i) < tmpMin) {
                        tmpMin = data.get(i);
                        minIndex = i;
                    }
                }
            }
            data.remove(index);
        }
    }

    public int top() {
        return data.get(index - 1);
    }

    public int getMin() {
        return data.get(minIndex);
    }

    @Override
    public String toString() {
        return data.stream().map(r -> {
            return r.toString();
        }).collect(Collectors.joining(",", "[", "]"));
    }
}
